package newcoder_exp.meituan;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

import org.junit.Test;

import linked.ListNode;

public class Meituan6 {
    //1. 找到一个数组中最大的n个数据
    /* 
        维护一个大小为n的小根堆。
        一旦堆满，比较新加入的元素与堆顶元素的大小，若大于堆顶，remove弔堆顶元素，并插入新元素，遍历所有数据后达到最后地结果
    */

    public List<Integer> topK(int[] nums, int k) {

        Queue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < nums.length; i++) {
            if (heap.size() < k) heap.offer(nums[i]);
            else {
                if (nums[i] > heap.peek()) {
                    heap.poll();
                    heap.offer(nums[i]);
                }
            }
        }
        return new ArrayList<>(heap);
    }

    //1.2 求频次的topK，需要将数据出现的最多的频次求出来。[lc 347]
    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            return null;
        }

        //需要一个修改元素的频次就能动态调整堆的结构。【频次只升不降】
        class MinHeap {
            class Node {
                int freq;
                int val;
                public Node(int freq, int val) {
                    this.freq = freq;
                    this.val = val;
                }
            }

            int capacity;
            Node[] heap;
            Map<Integer, Node> map;

            public MinHeap(int capacity) {
                this.capacity = capacity;
                this.heap = new Node[capacity];
                this.map = new HashMap<>();
            }

            public void insert(int val) {
                if (map.containsKey(val)) {
                    Node node = map.get(val);
                    node.freq++;
                    // adjust(node);
                } else {

                }
            }
        }
    }


    //2.两个栈实现一个队列
    public class Solution2 {
        Stack<Integer> stack1 = new Stack<Integer>();
        Stack<Integer> stack2 = new Stack<Integer>();
        
        public void push(int node) {
            stack1.push(node);
        }
        
        public int pop() {
            if (stack2.isEmpty()) {
                while(!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }


    // 3.删除 链表 倒数第N个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) return head;
        if (head.next == null) return n == 1 ? null : head;
        ListNode fast = head, slow = new ListNode(0);
        slow.next = head;
        int count = 0;
        while (fast != null) {
            fast = fast.next;
            count++;
            if (count == n) {
                break;
            }
        }
        if (count < n) {
            return head;
        }
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        if (slow.next == head) {
            return slow.next.next;
        }
        slow.next = slow.next.next;
        return head;
    }
    
    @Test
    public void test() {
        ListNode head = ListNode.newListNodeFromArray(new int[]{1,2,3,4,5});
        System.out.println(head);
        head = removeNthFromEnd(head, -1);
        System.out.println(head);
        AtomicInteger i;
    }
}
